[파이썬알고리즘인터뷰]#7-1 선형 자료구조
🔥 algorithm | February 18, 2021
문제 - 배열 파티션I
n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰수를 출력하라. (n = 2)
- ex)
[1, 4, 3, 2]이라는 배열이 있을 때 [1, 2], [3, 4] = 1 + 3 = 4
풀이 1 - 오름차순 풀이
def arrayPairSum(nums):
sum = 0
pair = []
nums.sort()
for n in nums:
pair.append(n)
if len(pair) == 2:
sum += min(pair)
pair = []
return sum
print(arrayPairSum([1, 4, 3, 2]))풀이 2 - 짝수 번째 값 계산
정렬된 상태에서는 짝수 값이 항상 작은 값이기 때문에 좀 더 효율적인 코드화가 가능
def arrayPairSum(nums):
sum = 0
nums.sort()
for i, n in enumerate(nums):
if i % 2 == 0:
sum += n
return sum
print(arrayPairSum([1, 4, 3, 2]))풀이 3 - 파이썬다운 방식
가장 코드가 짧으면서도 슬라이싱을 사용한 덕분에 성능 또한 가장 우수
def arrayPairSum(nums):
return sum(sorted(nums)[::2])
print(arrayPairSum([1, 4, 3, 2]))문제 - 자신을 제외한 배열의 곱
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
풀이 1 - 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
def productExceptSelf(nums):
out = []
p = 1
# 왼쪽 곱셈
for i in range(0, len(nums)):
out.append(p)
p *= nums[i]
p = 1
# 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
for i in range(len(nums) - 1, 0 - 1, -1):
out[i] *= p
p *= nums[i]
return out
print(productExceptSelf([1, 2, 3, 4]))문제 - 주식을 사고팔기 가장 좋은 시점
한번의 거래로 낼 수 있는 최대 이익을 산출하라.
풀이 1 - 브루트 포스로 계산
def maxProfit(prices):
max_price = 0
for i, price in enumerate(prices):
for j in range(i, len(prices)):
max_price = max(prices[j] - price, max_price)
return max_price
print(maxProfit([7,1,5,3,6,4]))가장 먼저 접근한 풀이는 브루트 포스 풀이. 처음부터 사고 팔고를 반복하고, 마지막에 최대 이익을 산출한다.
풀이 2 - 저점과 현재 값과의 차이 계산
import sys
def maxProfit(prices):
profit = 0
min_price = sys.maxsize
# 최솟값과 최댓값을 계속 갱신
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price - min_price)
return profit
print(maxProfit([7,1,5,3,6,4]))현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격 차이를 계산하고, 만약 클 경우 최대값을 계속 교체해나가는 형태로 풀이한다.
